package demo5;
import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
public class Solution {
    //1.把二叉搜索树转换为累加树
    private int sum;
    public TreeNode convertBST(TreeNode root) {
        //右 -> 根 -> 左  进行累加
        addSumTree(root);
        return root;
    }
    private void addSumTree(TreeNode root) {
        if(root == null) {
            return;
        }
        addSumTree(root.right);
        sum += root.val;
        root.val = sum;
        addSumTree(root.left);
    }

    //2.填充每个节点的下一个右侧节点指针 II(虚拟空结点 + 队列)
    public Node connect(Node root) {
        //BFS
        if(root == null) {
            return root;
        }
        Deque<Node> deque = new LinkedList<>();
        deque.offer(root);
        while(!deque.isEmpty()) {
            int size = deque.size();
            Node prev = null;//前置一个虚拟空结点
            while(size > 0) {
                Node node = deque.pollFirst();
                if(prev != null) {//为空说明还没有结点
                    prev.next = node;
                }
                prev = node;
                if(node.left != null) {
                    deque.offerLast(node.left);
                }
                if(node.right != null) {
                    deque.offerLast(node.right);
                }
                size--;
            }
        }
        return root;
    }
    //3.二叉搜索树中的插入操作(BFS)
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null) {
            return new TreeNode(val);
        }
        TreeNode cur = root;
        while(cur != null) {
            if(val < cur.val){
                if(cur.left == null) {
                    cur.left = new TreeNode(val);
                    break;
                }else {
                    cur = cur.left;
                }
            }else {
                if(cur.right == null) {
                    cur.right = new TreeNode(val);
                    break;
                }else {
                    cur = cur.right;
                }
            }
        }
        return root;
    }

    //4.N 叉树的层序遍历
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new LinkedList<>();
        if(root == null) {
            return ret;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new LinkedList<>();
            while(size > 0) {
                Node node = queue.poll();
                list.add(node.val);
                //放入每一个孩子
                for(int i = 0; i < node.children.size(); i++) {
                    queue.offer(node.children.get(i));
                }
                size--;
            }
            ret.add(new LinkedList<>(list));
        }
        return ret;
    }
    //5. 在每个树行中找最大值(BFS层序遍历)
    public List<Integer> largestValues(TreeNode root) {
        //层序遍历二叉树
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE;//记录每一层的最大值
            while(size > 0) {
                TreeNode node = queue.poll();
                if(node.val > max) {
                    max = node.val;
                }
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            list.add(max);
        }
        return list;
    }
    //6.剑指 Offer 68 - II. 二叉树的最近公共祖先(dfs)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == p || root == q) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
        //一个在左一个在右
        if(leftTree != null && rightTree != null) {
            return root;
        }
        //都在左树，说明左树就是公共祖先
        if(leftTree != null) {
            return leftTree;
        }else {//都在右树，说明右树就是
            return rightTree;
        }
    }
    //二叉树最大深度（预热）
    public int maxDepth1(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(maxDepth1(root.left), maxDepth1(root.right)) + 1;
    }
    public int maxDepth2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = maxDepth2(root.left);
        int right = maxDepth2(root.right);
        return Math.max(left, right) + 1;
    }
    //7.N 叉树的最大深度(dfs)
    public int maxDepth(Node root) {
        if(root == null) {
            return 0;
        }
        int depth = 0;
        //从根结点的所有子节点上取最大值
        for(int i = 0; i < root.children.size(); i++) {
            depth = Math.max(depth, maxDepth(root.children.get(i)));
        }
        return depth + 1;
    }
    //8.恢复二叉搜索树(显式层序遍历)
    private List<Integer> list = new ArrayList<>();
    private int index = 0;//list的下标
    public void recoverTree(TreeNode root) {
        //中序遍历保存到数组中
        dfs(root);
        //找到不正确的俩个数的索引
        List<Integer> changeIndex = fundError();
        //进行交换
        swap(changeIndex);
        //中序遍历进行覆盖
        cover(root);
    }//3 2 1
    private void cover(TreeNode root) {
        if(root == null) {
            return;
        }
        cover(root.left);
        root.val = list.get(index++);
        cover(root.right);
    }
    private void swap(List<Integer> changeIndex) {
        int index1 = changeIndex.get(0);
        int index2 = changeIndex.get(1);
        int tmp = list.get(index1);
        list.set(index1, list.get(index2));
        list.set(index2, tmp);
    }
    private List<Integer> fundError() {
        List<Integer> changeIndex = new ArrayList<>();
        int nums = -1;//零时保存
        for(int i = 0; i < list.size() - 1; i++) {
            if(nums == -1 && list.get(i) > list.get(i + 1)) {
                changeIndex.add(i);
                nums = i + 1;
            }else if(nums != -1 && list.get(i) > list.get(i + 1)) {
                changeIndex.add(i + 1);
            }
        }
        if(changeIndex.size() == 1) {
            changeIndex.add(nums);
        }
        return changeIndex;
    }
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }

    //9.二叉搜索树的范围和(dfs)
    private int sum;
    public int rangeSumBST(TreeNode root, int low, int high) {
        dfs(root, low, high);
        return sum;
    }
    private void dfs(TreeNode root, int low, int high) {
        if(root == null) {
            return;
        }
        if(root.val >= low && root.val <= high) {
            sum += root.val;
        }
        dfs(root.left, low, high);
        dfs(root.right, low, high);
    }

    //二叉搜索树的范围和
    public int rangeSumBST(TreeNode root, int low, int high) {
        if(root == null) {
            return 0;
        }
        if(root.val < low) {
            return rangeSumBST(root.right, low, high);
        }
        if(root.val > high) {
            return rangeSumBST(root.left, low, high);
        }
        //返回左子树的范围和和右子树的范围和
        return root.val + rangeSumBST(root.left, low, high)
                + rangeSumBST(root.right, low, high);
    }
    //10.二叉树的层平均值(BFS)
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            double size =(double) queue.size();
            double sizePrev = size;
            double avg = 0D;
            while(size > 0) {
                TreeNode node = queue.poll();
                avg += node.val;
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            list.add(1.0D * avg / sizePrev);
        }
        return list;
    }
}
